#include <bits/stdc++.h>

#define x first
#define y second
#define endl '\n'
#define int long long
#define NO {puts("NO"); return;}
#define YES {puts("YES"); return;}

using namespace std;

typedef long long ll;
typedef pair<int, int> PII;

const int mod = 1e9 + 7;
const int N = 1e6 + 10, INF = 1e18; 

int n, m;
int a[N], b[N];

int read()
{
	int x = 0, f = 1;
	char c = getchar();
	while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
	while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
	return x * f;
}

void solve()
{
	string s;
	int ans = 0;
	cin >> n >> m >> s;
	map<char, int> mp;
	for(int i = 0; i < n; i ++ ) mp[s[i]] ++ ;
	for(auto i : mp)
	{
		char now = i.x;
		if(i.y == 0) continue;
		if(now >= 'a') 
		{
			ans += min(mp[now], mp[now - 32]);
			int cnt = i.y;
			int cnt1 = mp[now - 32];
			mp[now] -= min(cnt, cnt1), mp[now - 32] -= min(cnt, cnt1);
		}
		else 
		{
			ans += min(mp[now], mp[now + 32]);
			int cnt  =i.y;
			int cnt1 = mp[now + 32];
			mp[now] -= min(cnt, cnt1), mp[now + 32] -= min(cnt, cnt1);
		}
	}
	int x = 0;
	for(auto i : mp)
	{
		int cnt = i.y;
		x += cnt / 2;
	}
	cout << ans + min(x, m) << endl;
	return;
}

signed main()
{
	ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
	int t = 1;
	cin >> t;
	while(t -- ) solve();
	return 0;
}